#!usr/bin/env python3
#-*- coding:utf-8 -*-
def heapSort(S):
    length=int(len(S))
    for i in range(length//2-1,-1,-1):
        adjustHeap(S,i,length)
    for j in range(length-1,-1,-1):
        S[0],S[j]=S[j],S[0]
        adjustHeap(S, 0, j)
    return S
    pass

def adjustHeap(S,i,length):
    temp=S[i]
    k=2*i+1
    while(k<length):
        if k+1<length and S[k]<S[k+1]:
            k+=1
            pass
        if S[k]>temp:
            S[i]=S[k]
            i=k
        else:
            break
            pass
        k=k*2+1
        pass
    S[i]=temp
    pass

'''
if __name__=='__main__':
    S=[1,5,4,3,8,7,6,2,9]
    newS=heapSort(S)
    print(newS)
'''